public class Test12 {
    static int N = 3;//部件数
    static int Suppliers = 3;//供应商数
    static int D = 4;//总价格限制
    static int minWeight = Integer.MAX_VALUE;//这个变量用来保存最小重量
    static int[][] weight = {{1, 2, 3}, {3, 2, 1}, {2, 1, 2}};//重量数组
    static int[][] value = {{1, 2, 3}, {3, 2, 1}, {2, 2, 2}};//价格数组
    static int[] str = new int[3];
    /*
    false表示选，true表示不选
     */
    //默认值是false
    //为什么是二维数组呢？因为要与w和v二维数组对应
    static boolean[][] flag = new boolean[3][3];

    //打印每个零件的供应商
    public static void output() {

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < Suppliers; j++) {
                if (flag[i][j])
                    str[i] = j + 1;
            }

        }
    }

    /*
    w：表示当前的重量
    v：表示当前的价值
    level：表示层数；0表示选第一个零件、1表示选第二个零件、2表示选第三个零件
     */
    public static void backtrack(int level, int w, int v) {
        //能走到这个if肯定是没超过限制重量D
        if (level == N) {
            int tmp = minWeight;
            minWeight = Math.min(minWeight, w);
            if (tmp != minWeight) {
                output();
            }
        } else {
            //表示从第一个供应商开始选择
            for (int i = 0; i < Suppliers; i++) {
                flag[level][i] = true;
                if (D >= v + value[level][i]) {
                    backtrack(level + 1, w +
                            weight[level][i], v + value[level][i]);
                }
                //这个为什么要改为false呢？
                //方便output方法的实现，找到每个零件的供应商
                flag[level][i] = false;
            }
        }
    }

    public static void main(String[] args) {

        backtrack(0, 0, 0);
        System.out.println("最小重量：" + minWeight);
        System.out.print("供应商顺序：");
        for (int i = 0; i < str.length; i++) {
            System.out.print(str[i] + " ");
        }
    }

}
